package com.zhj.structure.tree.utils;

/**
 * @PackageName:com.zhj.structure.tree.utils
 * @ClassName:BinaryTree
 * @auter: 朱慧杰
 * @date:2020/8/10 0010 10:02
 **/
public class ThreadedBinaryTree {
    // 中序线索化二叉树

    // 根节点
    private ThreadedNode root;
    // 用于零时存储前驱节点
    private ThreadedNode pre;

    public void setRoot(ThreadedNode root) {
        this.root = root;
    }

    // 中序线索化二叉树
    public void threadNodes() {
        threadNodes(root);
    }

    public void threadNodes(ThreadedNode node) {
        if (node == null) {
            return;
        }
        // 处理左子树
        threadNodes(node.leftNode);
        // 处理自己
        if (node.leftNode == null) {
            // 指向他的前驱
            node.leftNode = pre;
            // 指向他的前驱改变标记
            node.leftType = 1;
        }
        // 处理前驱节点的右指针
        if (pre != null && pre.rightNode == null) {
            pre.rightNode = node;
            pre.rightType = 1;
        }

        // 每处理一个节点，保存一下
        pre = node;
        // 处理右子树
        threadNodes(node.rightNode);
    }

    public ThreadedNode getRoot() {
        return root;
    }

    /*
        -------------------遍历二叉树
        递归的思想：
        前序遍历 ： 1, 2,4,5, 3,6,7
        中序遍历 ： 4,2,5, 1, 6,3,7
        后序遍历 ： 4,5,2, 6,7,3, 1
     */
    // 遍历不需要递归
    public void threadIterate() {
        ThreadedNode node = root;
        while (node != null) {
            while (node.leftType == 0) {
                node = node.leftNode;
            }
            System.out.print(node.getValue() + "\t");
            // 如果当前节点右指针指向后继节点，后继节点还可能有后继
            while (node.rightType == 1) {
                node = node.rightNode;
                System.out.print(node.getValue() + "\t");
            }
            // 替换
            node = node.rightNode;
        }
        System.out.println();
    }

}
